package sword.offer;

/**
 * 统计一个数字在排序数组中出现的次数。
 * @link https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftyThree {
    /**
     * 虽然是统计出现的次数 但因为是排序好的数组，那么相同的数字肯定挨着的，即将统计次数
     * 转换为<b>找边界问题<b/>
     * */
    class Solution {
        public int search(int[] nums, int target) {
            // 找到target的右边界 - target前一位的右边界 就是target出现的次数
            return getRight(nums, target) - getRight(nums, target-1);
        }
        public int getRight(int[] nums, int target){
            int left = 0, right = nums.length-1;
            while(left <= right){
                int mid = (left + right) / 2;
                if(target >= nums[mid]){ // 右边界在 [mid+1,right]
                    left = mid+1;
                }else{ // 右边界在 [left, mid-1]
                    right = mid-1;
                }
            }
            return left;
        }
    }
}
